// https://leetcode.cn/problems/decode-ways/

// 算法思路总结：
// 1. 动态规划求解数字解码方式总数
// 2. dp[i]表示前i个字符的解码方法数
// 3. 单独解码：当前字符非'0'时可从dp[i-1]转移
// 4. 组合解码：两位数字在10-26范围内可从dp[i-2]转移
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    int numDecodings(string s) 
    {
        if(s[0] == '0') return 0; 

        int n = s.size();
        vector<int> dp(n + 1);
        dp[0] = 1, dp[1] = 1;
        if(n == 1) return dp[1];

        for(int i = 2 ; i <= n ; i++)
        {
            if(s[i - 1] != '0') dp[i] += dp[i - 1];
            int tmp = (s[i - 2] -  '0') * 10 + (s[i - 1] - '0');
            if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];
        }
        return dp[n];
    }
};

int main()
{
    string s1 = "12", s2 = "226";
    Solution sol;

    cout << sol.numDecodings(s1) << endl;
    cout << sol.numDecodings(s2) << endl;

    return 0;
}